%!TEX root = ../book.tex
\chapter{Artificial Neural Networks}\label{chap:ann}

\textsl{Artificial neural networks (ANNs)}\index{Artificial Neural Networks} are part of a class of machine learning techniques that are loosely inspired by neural operation in the human brain; in robotics, they are generally used to classify or regress data for the dual purposes of perception (e.g., \cref{chap:vision,chap:feature_extraction}) and control (as will be shown in \cref{chap:taskexecution}).
%
While ANNs for the longest time have been just one of the many methods available to roboticists from the neighboring field of machine learning, recent advances in computing---in particular, graphical processing units (GPU)---and the availability of large datasets have enabled the training of neural networks with many layers, commonly referred to as \textsl{deep learning}\index{Deep Learning}. These (often massive) networks have led to revolutionary results in many fields including computer vision, natural language processing, video and speech processing, and robotics.
%
Not too long ago, neural networks were considered ``deep'' if the had just more than two layers. Today, ``deep'' neural networks can have hundreds of layers and thousands of inputs and outputs---or more!
This is still shy of the human brain, which contains $\sim 100^{11}$ neurons, each with thousands of synapses connecting a single neuron to thousands of others.

\begin{mdframed}
Remember: a \textsl{classification}\index{Classification (neural networks)} problem requires that input data be classified between two or more classes; a \textsl{regression}\index{Regression (neural networks)} problem requires a prediction of a (possibly continuous or high-dimensional) quantity. While a regression problem can be converted into a classification one (and vice versa), the machine learning community generally considers them two separate applications, and different techniques are developed to perform in each of these domains.
\end{mdframed}

Machine learning is a large field that shares many of its foundations with robotics, in particular for what concerns probability theory and statistics. Deep learning may be used as a drop-in replacement for sensor pre-processing and conditioning, computer vision and feature extraction, localization, and even replace controllers for locomotion and grasping.
For each of these applications, it is important to understand when deep learning may perform better than traditional approaches, and when it does not.
In a nutshell, deep learning models become first choice when not enough information exists to model a system using first principles. While a ``deep enough'' model with the right architecture might approximate any existing function in robotics, deep learning models lack ``explainability'' beyond statistical accuracy, that is, we may not easily be able to know how the approach actually works (in terms of which criteria it uses for its decisions) and when it might fail, usually making it a second choice behind an approach based on first principles with clear decision-making rationale.

The goals of this chapter are to introduce:

\begin{itemize}
    \item basic neural networks from the simple perceptron to multi-layer neural networks,
    \item different network architectures and encodings to tackle a variety of regression and classification tasks,
    \item convolutional neural networks---including padding, striding, pooling and flattening, and how they can be used to process spatial and temporal data,
    \item recurrent neural networks that introduce memory for classifying temporal data and perform control tasks.
\end{itemize}


\section{The simple Perceptron}

\begin{figure}[!b]
    \centering
    % \includegraphics[width=0.5\columnwidth]{figs/linearlyseparable}
    \def\svgwidth{0.6\textwidth}
    \import{./figs/}{linearlyseparable.pdf_tex}
    \caption{A 2-dimensional dataset, where every element has two values ($x_1$ and $x_2$) and belongs to one of two classes (red and blue). In the simplest case of linear separation, it is possible to separate the two classes with just a straight line.\label{fig:linearsep}}
\end{figure}

Artificial neural networks are inspired by neurons and synapses in the human brain and have been studied since the Fifties. One of the earliest models is the \textsl{Perceptron}\index{Perceptron}, which can classify an input vector $x$ of dimension $m$ into two classes. Such a problem is shown in \cref{fig:linearsep}. Variations of the simple perceptron remain the basic elements of deep neural networks until today.
%
As detailed in \cref{fig:perceptron}, a perceptron has $m$ inputs $x_1$ to $x_m$)---each modulated by a weight $w_1$ to $w_m$, as well as a threshold $b$; it outputs either zero or one.

\begin{figure}
    \centering
    % \includegraphics[width=0.5\columnwidth]{figs/perceptron.png}
    \def\svgwidth{0.66\textwidth}
    \import{./figs/}{perceptron.pdf_tex}
    \caption{The simple perceptron passes the dot product between the inputs $x$ and weights $w$ through a Heaviside function, returning 1 when $wx+b>0$ and 0 otherwise.}\label{fig:perceptron}
\end{figure}

The perceptron classifies whether $x$ lies above or below a hyperplane defined by the weights $w=\{w_1, \ldots, w_m\}$ using the following equation:
%
\begin{equation} \label{eq:heaviside}
f(x)=\begin{cases}
1 \qquad wx+b > 0\\
0 \qquad otherwise
\end{cases}
\end{equation}
%
Here, $wx=\sum_{i=1}^mw_ix_i$ is the dot product and the non-linear activation function $f(x)$ is also known as \index{Heaviside step function}\textsl{Heaviside step function}. In practice, we are appending the value of '1' to the vector $x$ so that $x_0=1$, which simplifies $wx+b$ (with $w=\{w_1, \ldots, w_m\})$ to $wx$ with $w=\{w_0, w_1, \ldots, w_m\}$ where $w_0$ takes the role of $b$. This is illustrated in \cref{fig:perceptron}, where the bias $b$ is alternatively labeled by $w_0$ and input $x_0=1$.

\subsection{Geometric interpretation of the simple perceptron}

If $w$ really defines an hyperplane, we should be able to easily visualize it when $m=2$. When $m=2$, i.e. every data point $x$ has only two dimensions, the separating hyperplane is a line such as the one shown in \cref{fig:linearsep}.
Indeed, we can easily demonstrate this. Writing the dot product out yields:
\begin{equation}
w_1x_1+w_2x_2+b=0
\end{equation}
As we plot $x_1$ along the x-axis and $x_2$ along the y-axis, we can write:
\begin{equation}
w_1x+w_2y+b=0
\end{equation}
This can be rewritten into:
\begin{equation}
y=-\frac{w_1}{w_2}x-\frac{b}{w_2}\quad ,
\end{equation}
and displayed within a scatter plot.

\subsection{Training the simple perceptron}

Training the perceptron, equates to finding appropriate values for $w$ and $b$ that separate the data into two classes. This process can be performed iteratively:

\begin{enumerate}
\item initialize all the weights with zeros or a small random number;
\item compute the prediction $y_j=f(wx_j+b)$ for each data point $x_j$. A suitable choice for $f()$ is the Heaviside step function , e.g. (\cref{eq:heaviside});
\item calculate the mismatch between prediction $y_j$ and the true class $d_j$ to update the weights:
\begin{equation}
w(t+1)=w(t)+r(d_j-y_j)*x_j
\end{equation}
\item repeat steps $2$ and $3$ until a termination criteria, e.g. a decreasing error or maximum number of iterations, is reached.
\end{enumerate}

Albeit very simple, this learning algorithm has still a lot in common with state-of-the-art algorithms. First, weights are updated in an iterative process using small increments governed by the parameter $r$, which is referred to as the \textsl{learning rate}\index{Learning Rate}. By changing $w$ in small increments, the algorithm is literally rotating and translating the separating line in a direction that minimizes the \textsl{loss}, given by $d_i-y_i$. One can easily see that if the learning rate is too low, the algorithm will never find a good solution. One can also see that if the learning rate is too large, the line might move too much, ``skipping'' the configuration that achieves optimal separation.

It is worth noting that this simple implementation is a \textsl{de facto} implementation of gradient descent\index{Gradient descent}---in this case with a loss function of the form $(d_i-y_i)^2$, that can be minimized by moving against the direction of its gradient, here $2(d_i-y_i)$. Other examples of gradient descent can be found in \cref{sec:kinematics:inverse:feedbackcontrol}.

Second, the learning algorithm requires multiple presentations of the data-set, as the error is computed for every point in the data set. The more the amount of data, the longer the training! In this case the increase in time is linear---which is also generally true for more complex and modern learning algorithms.

Third, the error between the prediction and the true class is only calculated based on the given training data. Even if we were to train with unlimited amounts of data points, it would still be difficult to generalizes for new data, and whether these new measurements will be distributed in a way that is representative of the training data.

\section{Activation Functions}\label{sec:activationfunctions}

Using a on-off Heaviside step function makes training a neural network using gradient descent rather difficult, as a function that switches from ``not working at all'' to ``working completely'' provides very little information in which direction to move. It is therefore more desirable to have a smoother activation function. One such function is the \index{Sigmoid function}\textsl{sigmoid function}:
\begin{equation}
\sigma(x)=\frac{1}{1+e^{-x}}
\end{equation}
Its main characteristics are that it asymptotically stays between $0$ and $1$, and crosses the y-axis at $0.5$. It is shown in \cref{fig:activationfunctions}, left.

\begin{figure}[htb]
    \centering
    % \includegraphics[width=0.9\columnwidth]{figs/activationfunctions}
    \def\svgwidth{0.9\textwidth}
    \import{./figs/}{activationfunctions.pdf_tex}
    \caption{Typical activation functions used in neural networks: the sigmoid activation function, left, and the rectified linear unit (ReLU), right.\label{fig:activationfunctions}}
\end{figure}

The sigmoid function is attractive for learning as the direction in which the weights should move to improve the error is very clear in the vicinity of $wx=0$, and computing its derivative is rather simple. While attractive in many cases, the sigmoid function has some drawbacks. For instance, when $wx$ is very large or very small, the neuron either saturates or never activates---a phenomenon known as the \textsl{vanishing gradient} problem. Another drawback is that computing the sigmoid function is computationally expensive. An alternative is the hyperbolic tangent $\tanh()$ which remains in the range of -1 to 1 and crosses the y-axis at 0.

A popular solution to decrease computation time is the \textsl{Rectified Linear Unit (ReLU)}\index{Rectified Linear Unit (ReLU)}, which is given by:
\begin{equation}
R(x)=max(0,x)
\end{equation}
and is shown in \cref{fig:activationfunctions}, right.
The dashed line indicates a refinement of the ReLU known as \textsl{leaky ReLU} with a typical slope of $0.1$; it improves learning for negative $wx$ by providing a directional gradient.

Please note that we only talk about ``perceptrons'' when the Heaviside step function is used as activation function.

\section{From the simple perceptron to Multi-layer neural networks}

We have seen that the single perceptron is able to linearly separate a dataset, returning ``$0$'' or ``$1$'' as a function of the data being below or above the separating hyperplane defined by the weight vector $w$. However, it is easy to see that some problems cannot be linearly separated.
%
\begin{figure}[htb]
    \centering
    % \includegraphics[width=0.9\columnwidth]{figs/xorproblem}
    \def\svgwidth{0.9\textwidth}
    \import{./figs/}{xorproblem.pdf_tex}
    \caption{Data that cannot be separated using a single line (left) in canonical form (center). This problem is known as the ``XOR'' problem due to the truth table of the associated classification problem (right).\label{fig:xorproblem}}
\end{figure}
%
In the example shown in \cref{fig:xorproblem}, the red and the blue data points are not separable by a single line, but require at least two lines. This problem is known as the ``XOR'' problem, which can be seen by looking at just four data points at $(0,0)$, $(0,1)$, $(1,0)$, and $(1,1)$. Tabulating this data together with its color, reveals a truth table with the characteristics of logical exclusive or (XOR), i.e. $x_1$ and $x_2$ have to be different for the output to be true (here ``blue''), whereas the output is false (here ``red'') when the inputs are the same.

We already know that a single perceptron can create a single separating hyperplane; we will therefore need at least two perceptrons to solve the XOR problem.
Using two perceptrons in parallel will yield us with tuples of the kind $(0,0)$, $(0,1)$ and so on; hence, we then need another perceptron to recombine these tuples into a single output.
\cref{fig:basicmultilayer} shows the simplest multi-layer perceptron that can be trained for the XOR problem, with one \index{Input Layer}\textsl{input layer}, a so-called\index{Hidden Layer} \textsl{hidden layer}, and an \index{Output Layer}\textsl{output layer}.

\begin{figure}
    \centering
    % \includegraphics[width=0.8\columnwidth]{figs/basicmultilayernetwork}
    \def\svgwidth{0.8\textwidth}
    \import{./figs/}{basicmultilayernetwork.pdf_tex}
    \caption{A simple multi-layer perceptron with one input layer, one hidden layer, and one output layer. \label{fig:basicmultilayer}}
\end{figure}

\subsection{Formal description of Artificial Neural Networks}

As with the simple perceptron, we will use node $i$'s bias as the $0-$th weight vector, that is:
\begin{equation}
w^k_{0,j}=b^k_j
\end{equation}
Here, we use the following notation: we denote the layer with a superscript, and the index of the incoming node and the outgoing node with a subscript tuple.
That is, $w^k_{i,j}$ is connecting the $i-$th incoming weight to the $j-$th node of the $k-$th layer (the $i-$th incoming weight is the $j-$th node in layer $k-1$). This, as well as the simple example network above, is illustrated in \cref{fig:backpropnotation}.
Each layer, denoted by the index $k$, has exactly $r^k$ nodes.
\begin{figure}[htb]
    \centering
    % \includegraphics[width=0.7\columnwidth]{figs/backpropnotation}
    \def\svgwidth{0.7\textwidth}
    \import{./figs/}{backpropnotation.pdf_tex}
    \caption{Notation used to index weights (left) with respect to layer $k$ and the multi-layer network from \cref{fig:basicmultilayer} (right).\label{fig:backpropnotation}}
\end{figure}

\subsubsection{Inputs and outputs}

The output $o_i$ of node $i$ is given by:
\begin{equation}
o_i=g(a_i^k)\quad,
\end{equation}
where $g()$ is a non-linear activation function such as---but not limited to---the ones described in \cref{sec:activationfunctions} or the Heaviside step function. Here, $a_i^k$ is known as the \textsl{activation}\index{Activation (neural network)}, i.e. the weighted sum computed by node $i$ in layer $k$:
\begin{equation}
a_i^k=\sum_{j=0}^{r_{k-1}}w_{j,i}^ko_j^{k-1}\quad,
\end{equation}
with $o_j^{k-1}$ the $j-$th output of the previous layer. This is illustrated in \cref{fig:backpropnotation2}.

\begin{figure}[htb]
    \centering
    % \includegraphics[width=0.7\columnwidth]{figs/backpropnotation2}
    \def\svgwidth{0.7\textwidth}
    \import{./figs/}{backpropnotation2.pdf_tex}
    \caption{Inputs and outputs of neuron $i$ in the $k$-th layer showing activation $a_i^k$ and output $o_i^k$.\label{fig:backpropnotation2}}
\end{figure}

In case of $k$ being the output layer, $o_i^k$ should be equivalent to $y_i^k$. Likewise, in case of $k-1$ being the input layer $o_i^{k-1}=x_i$.

\subsection{Training a multi-layer neural network}

Finding a set of weights and bias values, that is few parameters for a simple two-dimensional problem but potentially billions for a ``deep network'', is an NP-complete problem \cite{blum1992training}.
We therefore need an efficient approximation. To this end, we consider a training datasets consisting of input-output pairs $x_i$ and $y_i$ with $i=1..N$, and a feed-forward neural network with parameters $w$.

\subsubsection{Loss function}\label{sec:lossfunction}

The goal of training is to minimize an error function such as the mean squared error:
\begin{equation}
E(x,y,w)=\frac{1}{2N}\sum_{i=1}^{N}(\hat{y_i}-y_i)^2
\end{equation}
between the output $\hat{y_i}$ that the neural network with parameters $w$ computes and the known value $y_i$ from the \index{Training set}\textsl{training set} is minimized.
%
Similar to the perceptron, we can reduce $E(x,y,w)$ by iteratively descending along its gradient, i.e.:
\begin{equation}
w(t+1)=w(t)-\alpha \frac{\partial E(x,y,w(t))}{\partial w}
\end{equation}

This process is non-trivial, as calculating the partial derivatives across the computation graph of the neural network requires the chain rule. An algorithm known as \textsl{Backpropagation} is described in \cref{ch:backpropagation}.


\section{From single outputs to higher dimensional data}

Extending a neural network from one single output to multiple binary classifiers is straightforward, requiring only to increase the dimensionality of the output vector.
Much less straightforward is encoding more complex data which leads to the following question: how can we represent numerical values, such as digits from $0$ to $9$ or characters from A to Z?

\subsubsection{One-Hot Encoding}
A very common approach is known as \textsl{One-Hot Encoding (OHE)}. In OHE, $n$ discrete labels such as numbers or characters are encoded as a binary vector of length $n$. To encode the $i-$th element of a set of labels, this vector is zero except at position $i$. For example, to encode the characters $0 \ldots 9$, OHE would represent them as:

\begin{eqnarray}
\nonumber
0 &=& (1,0,0,0,0,0,0,0,0,0)\\
\nonumber
1 &=& (0,1,0,0,0,0,0,0,0,0)\\
\nonumber
2 &=& (0,0,1,0,0,0,0,0,0,0)\\
\nonumber
3 &=& (0,0,0,1,0,0,0,0,0,0)\\
\nonumber
4 &=& (0,0,0,0,1,0,0,0,0,0)\\
\nonumber
5 &=& (0,0,0,0,0,1,0,0,0,0)\\
\nonumber
6 &=& (0,0,0,0,0,0,1,0,0,0)\\
\nonumber
7 &=& (0,0,0,0,0,0,0,1,0,0)\\
\nonumber
8 &=& (0,0,0,0,0,0,0,0,1,0)\\
\nonumber
9 &=& (0,0,0,0,0,0,0,0,0,1)\quad .
\end{eqnarray}

\subsubsection{Softmax output}

Whereas OHE transforms the training input into a discrete probability distribution, nothing in the neural network will ensure that the data will also come out like that.
A sigmoidal activation function would ensure that each value remains between $0$ and $1$, but a ReLU does not. We therefore need a final layer that ensures each output to be limited to the range $0$ to $1$ \textsl{and} that the sum of all elements to be adding up to one. This is usually achieved using a so-called \textsl{Softmax}\index{Softmax (neural network)} layer. The softmax function is given by:

\begin{equation}
{\sigma (\mathbf {z} )_{j}={\frac {e^{z_{j}}}{\sum _{k=1}^{K}e^{z_{k}}}}} \quad for \quad j=1,\ldots,K
\end{equation}

That is, a vector $z \in \mathbb{R}^K$ will be converted into a $K-$dimensional vector whose $j-$th element is given by the above formula.

So, why not just normalize with the actual values, i.e. using $z_j$ instead of $e^{z_j}$, or, even easier, using $\arg \max_j$ to set the highest value of $z$ to $1$ and leave the rest to zero?
The reason is that each layer needs to remain differentiable for backpropagation to work.
Yet, the ``brutal'' cut-off introduced by the $\arg \max$ function is exactly what we want for the network to optimally match the training input. This is why the exponential function is used. It---literally---exponentially emphasizes larger values over smaller values, making the class with the highest probability stand out.

\section{Objective functions and optimization}

The key idea to train neural networks is to change the network's parameters so that a certain objective function (called loss function), is minimized.
This is usually done by evaluating the gradient of the objective function with respect to the network's parameters. Being differentiable is therefore a key requirement for a useful objective function.
However, the magnitude of the weights can dramatically impact neural network performance and finding this magnitude is entirely dependent on the type of learning problem.

\subsection{Loss functions for regression tasks}

So far, we have considered the so-called \textsl{Mean-squared Error} (MSE):

\begin{equation}
E=\frac{1}{2N}\sum_{i=1}^{N}(\hat{y_i}(w)-y_i)^2\quad ,
\end{equation}

which is the average error over a set of $N$ pairs of predictions $\hat{y}$ that are dependent on the network parameters $w$ and known values $y$---see also \cref{sec:linefitting}. This function is particularly convenient, as the square makes it convex, allowing to find its minimum by following its gradient (``gradient descent'').

MSE is most suited for \textsl{regression} tasks\index{Regression} in which data points are fitted to a model such as a line. Using a sigmoid or other continuous activation function, the error for each class can also be interpreted as a distance from the separating hyperplane, which makes MSE also suitable (but not optimal) for these kind of tasks. An example is illustrated below:

\begin{figure}[htb]
    \centering
    % \includegraphics[width=0.8\columnwidth]{figs/backpropnotation3}
    \def\svgwidth{0.5\textwidth}
    \import{./figs/}{outliers.pdf_tex}
    \caption{A regression problem with an outlier.\label{fig:outliers}}
\end{figure}

From \cref{fig:outliers} it is clear that MSE poorly deals with outliers. If one value deviates largely from the prediction, the quadratic term in MSE will heavily ``punish'' this value. An alternative to MSE is the \textsl{Mean Absolute Error} (MAE):

\begin{equation}
E=\frac{1}{2N}\sum_{i=1}^N\|\hat{y_i}(w)-y_i\|)
\end{equation}

Here, the absolute value ensures that the error is always positive no matter the direction, but large errors are weighted on the same order of magnitude as smaller ones. MAE is therefore better suited if your training set contains outliers.

In practice, a large variety of loss functions have been developed to combine features of both MSE and MAE; in the simplest form of the \textsl{Huber loss}\index{Huber Loss (neural networks)} function, this is achieved via a simple piecewise combination.

\subsection{Loss functions for classification tasks}

Although a classification task can be cast into a regression problem, classifying is more akin to throwing a dice.
Indeed, the output of the Softmax layer is a discrete probability distribution in which each element $y_i=(p_0, \dots, p_c, \dots ,p_N)$ is the probability of an instance $x_i$ to be of class $c$ in $N$ classes total.

We speak of the \textsl{entropy}\index{Entropy (neural networks)} of a probability distribution as the amount of ``variety'' that we expect.
To make an example, a uniform distribution has the highest entropy because there exist a high number of possible outcomes, whereas the one-hot encoded vectors are probability distributions with very low entropy.
The entropy of the distribution of $y_i$ (the training vector that stores the true class $c$ for each instance $x_i$) is given by:

\begin{equation}
H(y_i)=-\sum_{c=1}{N}p_c \log p_c\quad.
\end{equation}

Here, the logarithm can be of basis ten or two. In any case, the entropy function has a couple of interesting properties: first, the logarithm from $0$ (negative infinity) to $1$ is negative (this is why probabilities yield positive values). Second, the logarithm of $1$ is zero, i.e., a distribution with only one element ($p_c=1$) has the lowest possible entropy.
Third, the lower the individual entries for $p_c$ are---for example, in a uniform distribution where $p_c=\frac{1}{N}$, the higher the entropy.

In every dataset, there will always exist a true distribution $P(C=i)$ that the data is distributed according to. By classifying every element in the training set, the neural network also generates its own distribution or ``interpretation'' of the data.
Ideally, in the case of a $100\%$ fit, the neural network will generate (or ``learn'') the exact same distribution as the one that describes the training set. In the worst case, the network will generate a distribution that is completely different. Evaluating a neural network's performance is therefore a matter of comparing two probability distributions.

One way to compare two distributions is via their entropy---a process known as \textsl{cross entropy}:
\begin{equation}
H(\hat{y},y)=-\sum_{i=1}{N}y_i\log \hat{y_i}\quad ,
\end{equation}

with $y_i=p_i$ being the known probability for instance $x$ to be class $i$ and $\hat{y_i}$ being the prediction. As the neural network will never perfectly represent the data, the cross entropy will always be larger than the entropy of the true distribution, that is:
\begin{equation}
H(y)-H(\hat{y},y) \leq 0
\end{equation}

This difference between the entropy of the true distribution and the cross-entropy between the true and the estimated distribution is known as \textsl{Kullback-Leibler Divergence}\index{Kullback-Leibler Divergence}. It is a measure of dissimilarity between two distributions.

\subsection{Binary and Categorical cross-entropy}
In the case where there are only two classes, the \textsl{binary cross-entropy} is calculated as follows:
\begin{equation}
H(\hat{y},y)=-\sum_{i=1}^Ny_i\log(\hat{y_i})=-y_1\log(\hat{y_1})-(1-y_1)\log(1-\hat{y_1})
\end{equation}

As there are only two classes (either true or false), $\hat{y_2}$ directly follows from $1-\hat{y_1}$.
The more general case for $N>2$ is known as \textsl{categorical cross-entropy}.
%
When using one-hot encoding, only class $c$ has probability 1 ($y_c=1$), reducing the cross-entropy to:
\begin{equation}
H(\hat{y},y)=-\log(\hat{y_c})
\end{equation}

with $c$ the true class (the other terms are zero). 
Combined with the softmax activation function the categorical cross entropy therefore computes as
\begin{equation}
H(\hat{y},y) = -\log\left(\frac{e^{\hat{y_c}}}{\sum_{j}^N e^{\hat{y_j}}}\right)
\end{equation}

\section{Convolutional Neural Networks}\label{sec:ann:cnn}

A drawback of the ANN architectures that we have covered so far is that they do not consider the spatial information that might be hidden in a dataset.
For example, as detailed in \cref{chap:vision}, in the context of vision it is important to interpret the value of a certain pixel depending on what can be seen nearby: a blue pixel surrounded by white ones might be an eye, whereas a blue pixel surround by blue ones might be an ocean. In addition to color, neighboring pixels also encode structure. When looking at the MNIST dataset (a collection of hand-drawn numbers from zero to nine), we might for example be looking for crosses (such as the center of an eight), T-shaped junctions (such as in the letter four) or half-circles (like in the letter three), whose number might then serve as features for our neural network.
The SIFT features in \cref{chap:feature_extraction} were a good example of a hand-coded approach to encode such spatial information. We will now see how ANNs can find such features automatically.

If you recall, one way to extract features in image processing is by \textsl{convolving} an image with a \textsl{kernel}\index{Kernel (neural networks)}---see e.g. a convolution with a $3\times3$ and a $7\times7$ kernel in \cref{fig:convolution}.
%
\begin{figure}[htb]
    \centering
    % \includegraphics[width=0.8\columnwidth]{figs/backpropnotation3}
    \def\svgwidth{0.8\textwidth}
    \import{./figs/}{convolution.pdf_tex}
    \caption{Convolution with a $3\times3$ and a $7\times7$ kernel and resulting reduction in image size.\label{fig:convolution}}
\end{figure}
%
During a convolution, the kernel is swept across the input image, summing over a piece-wise multiplication of each element of the kernel with the underlying image pixels (see also \cref{chap:vision}). As all multiplications are summed, such an operation yields only one pixel. As the kernel has to start somewhat inside the image (unless its borders are padded with appropriate values), we are loosing half the width of the kernel on each side. In the example above, a $3\times3$ kernel turns a $28\times28$ input image into a $26\times26$ output image and a $7\times7$ kernel turns it into a $22\times22$ pixel image. Mathematically, the convolution is defined as

\begin{equation}
x(n_1,n_2)*h(n_1,n_2)=\sum_{k_1=-\infty}^{\infty} \sum_{k_2=-\infty}^{\infty} h(k_1,k_2)x(n_1-k_1,n_2-k_2)
\end{equation}

where bounds (here, infinity) need to be chosen so that the kernel starts at the upper left corner of the image and ends at the lower right corner. It is also possible to artificially grow the input image by adding pixels around it, which is known as \textsl{padding}. Note that the resulting output is identical to examples shown in \cref{chap:vision}.

\subsection{From convolutions to 2D neural networks}

When looking at how one individual pixel in the output above gets computed, we assume that the input pixel is labeled $x_{i,j}$ with $i$ the row and $j$ the column of this pixel. We also assume the entries of the convolution kernel to be indexed in a similar way. Using a $3\times3$ kernel, the first pixel of the output is then calculated by:

\begin{eqnarray}
o_{0,0}=&x_{0,0}w_{0,0}+x_{0,1}w_{0,1}+x_{0,2}w_{0,2}\\
\nonumber
		&+x_{1,0}w_{1,0}+x_{1,1}w_{1,1}+x_{1,2}w_{1,2}\\
\nonumber
		&+x_{2,0}w_{2,0}+x_{2,1}w_{2,1}+x_{2,2}w_{2,2}
\end{eqnarray}

This operation is therefore simply computing the dot-product of the value of $9$ pixels with the kernel weights. Adding a bias value and an activation function such as ReLu is therefore identical to adding a hidden layer with nine neurons!

Performing the convolution by moving the convolution kernel with a width of ($2r+1$) across an entire $X\times Y$ image is therefore akin to creating $(X-2r)(Y-2r)$ ``convolutional'' neurons; the resulting structure is called a \textsl{feature map}\index{Feature Map (neural networks)}.
Note that the ``weights'' of the feature map---i.e., the entries of the kernel matrix---are identical for each neuron in the feature map. We can now repeat this step with additional kernels, resulting in multiple feature maps, which then form a \textsl{convolutional layer}\index{Convolutional Layer (neural networks)}.

Importantly, as this structure is very similar to the conventional neural network structure (except for the fact that a large number of weights are identical), the parameters of each kernel can also be trained using backpropagation! See \cref{sec:backpropagation}.

\subsection{Padding and striding}

As mentioned earlier, a convolution of kernel width $2r+1$ reduces the input by $r$ on each side.
If this is not desired (for example, when multiple convolutional layers are used in series), \textsl{padding} can be used to surround the input image with up to $r$ pixels, which results in the output image having the same dimension as the input image. Instead of moving the convolution kernel pixel by pixel, skipping pixels will further reduce the size of the output image. The amount by which the convolution kernel is moved is known as \textsl{stride}. This is illustrated in \cref{fig:stride} for strides of one and three.

\begin{figure}[htb]
    \centering
    % \includegraphics[width=0.8\columnwidth]{figs/backpropnotation3}
    \def\svgwidth{0.8\textwidth}
    \import{./figs/}{stride.pdf_tex}
    \caption{Convolution with $1\times1$ and $3\times3$ stride and resulting output.\label{fig:stride}}
\end{figure}

\subsection{Pooling}

The feature maps that result from convolution each identify specific features that are defined by their kernels.
Though training, it is possible to identify these kernels and specialize them for specific characteristics that are of interest: some might ``fire'' on edges, others on intersections of lines, and others on very specific patterns in the dataset.
Activation functions may be used to further amplify this effect, making a clear distinction between whether a feature is present or not.
However, in most practical applications such features are rather sparse, and whether they exist in a larger area or not might the most salient information. This can be achieved by a \textsl{pooling layer}\index{Pooling (neural networks)}.

A pooling operation applies a window to select the maximum (in which case it is referred to as \textsl{MaxPooling}\index{Max Pooling (neural networks)}) or the average, among many other possible non-linear functions, from a window of a given size. \cref{fig:pooling} shows the result of a MaxPooling layer with pool size of $3\times3$ and stride lengths of $1\times1$ and $3\times3$. Usually, the stride length is the same as the width of the window.

\begin{figure}[htb]
    \centering
    % \includegraphics[width=0.8\columnwidth]{figs/backpropnotation3}
    \def\svgwidth{0.8\textwidth}
    \import{./figs/}{pooling.pdf_tex}
    \caption{Pooling using a pool size of $3\times3$ for different strides and corresponding output.\label{fig:pooling}}
\end{figure}

Although the $max()$ function is not differentiable, MaxPooling can still be used in backpropagation by selectively passing the gradient to only the neuron that has shown to have the maximum activation and setting the gradient of all other neurons to zero. When an averaging pooling function is used, the gradient is divided among all neurons in the pool in equal parts.

\subsection{Flattening}

The first step in previous neural network models has been to flatten a 2D input image into a one-dimensional vector. This has been the precondition to apply a dense layer and has been accomplished during preprocessing.
However, CNNs require multi-dimensional inputs (e.g., 2D images with multiple color channels). Turning a multi-dimensional tensor into a vector is known as \textsl{flattening} and results into simple reordering. For example, an RGB image of dimensionality ($28\times28\times3$) might be turned into $20$ convolutional filters, or $2352$ individual neurons. A flattening layer arranges them again in a single vector.

\subsection{A sample CNN}

\cref{fig:cnn} shows a typical CNN that combines multiple convolutional and pooling layers. The network takes a $28\times28$ image as an input and trains $20$ different $5\times5$ convolution kernels to create $20$ feature maps of $28\times28$ each. This layer is followed by a maxpooling layer that downsamples each feature map by a factor of two. These feature maps are then convolved with $50$ $5\times5$ convolution kernels to create $50$ $14\times14$ feature maps. These will again be downsampled by a maxpooling operation. The resulting $50$ feature maps are then flattened and fed into a hidden layer of 500 neurons, and finally into a SoftMax-activated output layer with $10$ neurons.

\begin{figure}[htb]
\tiny
    \centering
    % \includegraphics[width=0.8\columnwidth]{figs/backpropnotation3}
    \def\svgwidth{\textwidth}
    \import{./figs/}{cnn.pdf_tex}
    \caption{A typical convolutional neural network taking a $28\times28$ input image and reducing it to $10$ classes.\label{fig:cnn}}
\end{figure}

\subsection{Convolutional Networks beyond 2D image data}

Convolution kernels emphasize areas of similarity. This can be readily understood when considering a simple kernel like $[[0,9,0],[0,9,0],[0,9,0]]$ which emphasizes vertical lines but ignores horizontal ones. Training a convolutional network therefore automatically finds regularities in the training set, as well as in the resulting feature map---often generating hierarchical representations by itself. A common example is a convolutional neural network for face detection in which early layers detect low-level features, which then get recombined into noses, ears, mouth and eyes in deeper layers.

Convolutional neural networks are not limited to 2D image data, but can also be applied to 1D time series. Here, the will find distinct patterns, for example peaks in an accelerometer or gyroscope reading, which can then be used collectively to classify complex signals.

\section{Recurrent Neural Networks}

So far, we have only worked with static data. Even if data had a temporal nature, we have simply concatenated inputs and looked at a piece of history all at once. When using a dense network, all inputs are initially of equal importance and it is up to the network to identify salient information. Albeit convolutional layers might help to dictate some sense of order---a 1D convolutional layer might as well be interpreted as detecting a pattern in a timeseries---dense layers focus on the values of individual features, not on the order of information.

For example, it is straightforward to train a neural network controller to transform input data from sensors into motor commands to perform tasks like light following, obstacle avoidance, and wall following such as those described in \cref{chap:taskexecution}; however, such a controller will be purely reactive and not be able to, for example, escape a U-shaped obstacle.

To overcome this limitation, it is useful to introduce a notion of state in a neural network. In this case, the detection of an event such as ``getting stuck'' may be used to modify the network state in some way. This is accomplished using so-called \textsl{recurrent neural networks}\index{Recurrent neural network}\index{RNN}.
A recurrent neural network uses a special kind of neuron, which sums the input $x_t$ at time $t$ with the value of the hidden state $h_{t-1}$ at the previous time step $t-1$ to compute a hidden state $h_t$ at time $t$. Both terms of this sum are weighed by weights W and U. The output of the recurrent layer is the hidden state $h_t$ weighed by a third weight V and ran through a second activation function. The equation below shows the computation of a RNN layer in vector form, passing the hidden states through a softmax activation.

\begin{equation}
h_t = \tanh(Wh_{t-1}+Ux_t)
\end{equation}
\begin{equation}
y_t = softmax(Vh_t)
\end{equation}

This relationship is shown in \cref{fig:rnn}. As an RNN cell is reusing its internal state $h_t$ in the next iteration, a network that looks back $N$ time-steps is modeled as $N$ cells that are laterally connected. As this is how an RNN is actually implemented, the data from all time steps is presented at the same time.

\begin{figure}
\tiny
    \centering
    % \includegraphics[width=0.8\columnwidth]{figs/backpropnotation3}
    \def\svgwidth{\textwidth}
    \import{./figs/}{rnn.pdf_tex}
    \caption{A sample recurrent neural network (left) and its expanded version (right) that is looking back four time steps. \label{fig:rnn}}
\end{figure}

\section*{Take-home lessons}
\begin{itemize}
\item Artificial Neural Networks and the tools associated with them have become a powerful tool to skip modeling a system using first principles, but simply learn its properties from data. As such, they are capable of replacing many of the models discussed in previous chapters, ranging from kinematics to vision, feature detection, and controls.
\item Simple neural networks are capable of both classification and regression akin to techniques described in \cref{chap:feature_extraction}, whereas convolutional networks are capable of filtering and pre-processing techniques such as described in \cref{chap:vision}.
\item When a system is not purely reactive but requires state such as those described in \cref{chap:taskexecution}, recurrent neural networks are needed to implement a notion of memory.
\end{itemize}
\section*{Exercises}\small
\begin{enumerate}
\item Implement the simple perceptron training algorithm and use it to find a separating hyperplane for simple data.
\item Find out how to implement the auto differentiation (or auto gradient) function in your favorite numerical package, e.g. \textsl{NumPy} or \textsl{PyTorch} to automatically calculate the derivative of your loss function.
\item Use a machine learning package of your choice to train a classifier for synthetic images such as the ``Ratslife'' landmarks. If you can, use a real robot to generate appropriate training data.
\item Select a simple 2D target, e.g. a cross on white background, and record images from different distances and angles. Can you train a CNN to predict these two quantities from your image?
\item Select a pre-trained image classifier from your preferred machine learning toolkit and use it as the basis to train your classifier for either landmark recognition or pose recognition. How does using a pre-trained classifier affect learning time and accuracy?
\item What kind of network architecture would you chose to track the robot's location (odometry) based on encoder inputs?
\item Download the ``Robot Execution Failures Data Set'' from the UCI machine learning repository. It contains time-series data from a robot's force-torque sensor as well as whether manipulation was successful. Define a recurrent neural network architecture for this data and train it.
\end{enumerate}\normalsize


